
/**
 * https://leetcode.cn/problems/count-special-integers
 * 2376. 统计特殊整数
 */
class Solution {
public:
    int res;  // 用于记录不含重复数字的整数数量
    int a[12];  // 用于存储 n 的每一位数字
    int vis[12];  // 用于标记当前位是否已经使用过

    // 函数 wei 用于将整数 x 转换为数组 a，并返回 x 的位数
    int wei(int x) {
        int cnt = 0;
        while (x) {
            cnt++;
            a[cnt] = x % 10;  // 获取当前位的数字
            x /= 10;  // 去掉当前位
        }
        return cnt;
    }

    // 深度优先搜索函数 dfs
    void dfs(int cur, int n, int k) {
        if (cur > n) {  // 如果当前位超过了 n 的长度
            res++;  // 找到了一个不含重复数字的整数
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (cur == 1 && i == 0) k = 0;  // 第一位不能是 0
            if (cur == 1 && i >= a[cur]) k = -1;  // 如果第一位大于等于 n 的第一位，进入限制状态

            if (k == 0) {  // 不受限制状态
                if (vis[i] == 0 || i == 0) {  // 当前数字未使用过或为 0
                    vis[i] = 1;  // 标记当前数字已使用
                    if (i == 0) dfs(cur + 1, n, 0);  // 如果当前数字为 0，继续不受限制
                    else dfs(cur + 1, n, 1);  // 否则进入受限状态
                    vis[i] = 0;  // 回溯，取消标记
                }
            } else if (k == -1) {  // 受限状态
                if (vis[i] == 0 && i <= a[cur]) {  // 当前数字未使用过且小于等于 n 的当前位
                    vis[i] = 1;  // 标记当前数字已使用
                    if (i == a[cur]) dfs(cur + 1, n, -1);  // 如果当前数字等于 n 的当前位，继续受限
                    else dfs(cur + 1, n, 1);  // 否则进入不受限状态
                    vis[i] = 0;  // 回溯，取消标记
                }
            } else {  // 其他情况
                if (vis[i] == 0) {  // 当前数字未使用过
                    vis[i] = 1;  // 标记当前数字已使用
                    dfs(cur + 1, n, 1);  // 继续不受限
                    vis[i] = 0;  // 回溯，取消标记
                }
            }
        }
    }

    // 主函数 numDupDigitsAtMostN 计算从 1 到 n 之间所有包含重复数字的整数数量
    int numDupDigitsAtMostN(int n) {
        int k = wei(n);  // 获取 n 的位数
        reverse(a + 1, a + 1 + k);  // 将 a 数组反转，使其从高位到低位
        dfs(1, k, 1);  // 从第 1 位开始进行 DFS
        return n - res + 1;  // 返回包含重复数字的整数数量
    }
};